#include <stdlib.h>
#include <stdio.h>

#include <assert.h>

#include "iterbintreeKM.h"

#define NO_MANS_LAND    0xdeadbeef

/*-------------------------------------------------------------------*/
/*                            Structs                                */
/*-------------------------------------------------------------------*/

typedef struct Node_t
{
    void*          m_data;
    struct Node_t* m_small;
    struct Node_t* m_big;
    struct Node_t* m_parent;
}Node;

struct BinTree_t
{
    Node*   m_begin;                        /* pointer to smallest node in the tree                               */
    Node    m_end;                          /* node indicates forbidden place, one after the largest node in tree */
    Node*   m_root;                         /* pointer to the root                                                */
    Less_t  m_func;                         /* pointer to compare func                                            */
};

enum {SEARCH = 0, INSERT = 1};              /* modes for SearchInsert function */

/********************************************************************/
/*                 Internal Functions Declaration                   */
/********************************************************************/

/*------------------------------------------------------------------*/
/*  Alloc mem for new node and initializes it.                      */
/*  If alloc failes 0 is returned                                   */
/*------------------------------------------------------------------*/
static Node*   BinTreeCreateNode(void* _data);

/*------------------------------------------------------------------*/
/*  Function inserts _node as root in the tree                      */
/*------------------------------------------------------------------*/
static Node*   BinTreeInsertRoot(BinTree* _btree,Node* _node);

/*------------------------------------------------------------------*/
/*  Recursive function makes Search or Insert of a specific         */
/*  node in the tree depending on the _mode.                        */
/*  for _mode = SEARCH:                                             */
/*  Function returns the pointer to first found node, if node       */
/*  wasn't found 0 is returned                                      */
/*  for _mode = INSERT:                                             */
/*  Function inserts the _node in right place in the tree, pointer  */
/*  to inserted node is returned                                    */
/*------------------------------------------------------------------*/
static Node*   BTSrchInsertNode(BinTree*_btree, Node* _root, Node* _node, int _mode);

/*------------------------------------------------------------------*/
/*  In INSERT mode : function makes insertion of the node to one    */
/*  of the direction fields (big/small) of the parent.              */
/*  In SEARCH mode : function returnes invalid iterator             */
/*------------------------------------------------------------------*/
static Node*   BTSrchInsertRtrn(BinTree* _btree,Node* _parent,Node** _direcPtr,Node* _insNode,int _mode);

/*------------------------------------------------------------------*/
/*  Recursive deletes the nodes of the subtree in postorder         */
/*------------------------------------------------------------------*/
static void    BTSubtreeDel(BinTree* _btree,Node* _node);

/*------------------------------------------------------------------*/
/*  Function searches for next largest node in the big subtree      */
/*  of the given node.                                              */
/*------------------------------------------------------------------*/
static Node* BTNextBigChild(Node* _bigNode);

/*------------------------------------------------------------------*/
/*  Function searches for prev largest node in the small subtree    */
/*  of the given node.                                              */
/*------------------------------------------------------------------*/
static Node* BTPrevBigChild(Node* _smallNode);

/*------------------------------------------------------------------*/
/*  Function deletes node and exchanges it with it's child.         */
/*------------------------------------------------------------------*/
static void  BTUpSubTree(BinTree* _btree, Node* _node, Node* _child);

/*********************************************************************/
/*                      Functions Implemetation                      */
/*********************************************************************/

BinTree* BinTreeNew(Less_t _func)
{
    BinTree* btree = 0;

    assert(_func);
    btree = (BinTree*)calloc(1,sizeof(btree[0]));
    if (!btree)
    {
        return 0;
    }

    btree->m_func         = _func;
    btree->m_root         = 0;
    btree->m_begin        = &btree->m_end;
    btree->m_end.m_data   = (void*)NO_MANS_LAND;
    btree->m_end.m_parent = (Node*)NO_MANS_LAND;

    return btree;
}

/*-------------------------------------------------------------------*/

BTreeIt BinTreeInsert(BinTree* _btree,void* _data)
{
    Node* node;

    assert(_btree);
    assert(_data);

    node = BinTreeCreateNode(_data);                        /* create new node amd init it */
    if (!node)
    {
        return BinTreeEnd(_btree);
    }

   if (BinTreeIsEmpty(_btree))                              /* insert node as root */
    {
        return (BTreeIt)BinTreeInsertRoot(_btree,node);
    }

    BTSrchInsertNode(_btree,_btree->m_root,node,INSERT);    /* insert node in subtree */

    if (node == _btree->m_begin->m_small)                  /* update begin pointer */
    {
        _btree->m_begin = node;
        _btree->m_begin->m_small = &_btree->m_end;

        return (BTreeIt)node;
    }

    if (node == _btree->m_end.m_parent->m_big)             /* update end of the list */
    {
        node->m_big = &_btree->m_end;
        _btree->m_end.m_parent = node;
    }

    return (BTreeIt)node;
}

/*-------------------------------------------------------------------*/

BTreeIt BinTreeFind (BinTree* _btree, void* _data)
{
    Node* node = 0;

    assert(_data);
    assert(_btree);

    node = BinTreeCreateNode(_data);
    if (!node)
    {
        return BinTreeEnd(_btree);
    }

    return (BTreeIt)BTSrchInsertNode(_btree,_btree->m_root,node,SEARCH);
}

/*-------------------------------------------------------------------*/

int BinTreeIsEmpty(BinTree* _btree)
{
    assert(_btree);

    return (_btree->m_begin == &_btree->m_end);
}

/*-------------------------------------------------------------------*/

void* BinTreeGetData(BTreeIt _it)
{
    assert(_it);

    return ((Node*)_it)->m_data;
}

/*-------------------------------------------------------------------*/

void BinTreeDel(BinTree* _btree)
{
    assert(_btree);

    if (!BinTreeIsEmpty(_btree))
    {
        BTSubtreeDel(_btree,_btree->m_root);
    }

    free(_btree);
}

/*-------------------------------------------------------------------*/

void BTSubtreeDel(BinTree* _btree, Node* _node)
{
    if ( (!_node->m_small || _node->m_small == &_btree->m_end)  &&
         (!_node->m_big   || _node->m_big   == &_btree->m_end))
    {
        _node->m_data = (Node*)NO_MANS_LAND;
        free(_node);
        return;
    }

    if (_node->m_small)                                 /* free all the nodes in left subtree */
    {
        BTSubtreeDel(_btree,_node->m_small);
    }
    if (_node->m_big)                                   /* free all the nodes in right subtree */
    {
        BTSubtreeDel(_btree,_node->m_big);
    }

    _node->m_data = (Node*)NO_MANS_LAND;
    free(_node);                                        /* free parent node */
    return;
}

/*-------------------------------------------------------------------*/

BTreeIt   BinTreeRemove (BinTree* _btree, BTreeIt _it)
{
    BTreeIt nextIt  = 0;
    BTreeIt prevIt  = 0;
    Node*   node    = 0;

    assert((Node*)_it);
    assert(_btree);

    node   = (Node*)_it;
    nextIt = BinTreeNext(_it);
                                                /* the node has two subtrees */
    if (node->m_big && node->m_small && node->m_big != &_btree->m_end)
    {
        node->m_data = ((Node*)nextIt)->m_data;
        BinTreeRemove(_btree,nextIt);           /* move up inorder successor */

        return (BTreeIt)node;
    }

    if (node == _btree->m_begin)                /* update begin */
    {
        _btree->m_begin = (Node*)nextIt;
    }

    if (_btree->m_begin == &_btree->m_end)      /* last node in tree update root */
    {
        free(node);
        _btree->m_root = 0;

        return nextIt;
    }
                                                /* node has only valid small subtree */
    if (!node->m_big || node->m_big == &_btree->m_end)
    {
        if (node->m_big == &_btree->m_end)      /* node to be deleted is the largest in the tree */
        {
            prevIt = BinTreePrev(_it);          /* update end to prev node */
            _btree->m_end.m_parent = (Node*)prevIt;
        }
        BTUpSubTree(_btree,node,node->m_small); /* move up small subtree */
        _btree->m_end.m_parent->m_big = &_btree->m_end;

        return nextIt;
    }

    BTUpSubTree(_btree,node,node->m_big);       /* move up big subtree or delete node with no children */

    return nextIt;
}
/*-------------------------------------------------------------------*/

void BTUpSubTree(BinTree* _btree, Node* _node, Node* _child)
{
    assert(_node);

    if (_node == _btree->m_root)                /* node to be deleted is root */
    {
        _btree->m_root   = _child;              /* update root */
        free(_node);

        return;
    }
    if (_node->m_parent->m_small == _node)      /* make connection from node parent to child from */
												/* small side or big side 						  */
    {
        _node->m_parent->m_small = _child;
    }
    else
    {
        _node->m_parent->m_big = _child;
    }

    if (_child && _child != &_btree->m_end)
    {
        _child->m_parent = _node->m_parent;
    }

    _node->m_data = (void*)NO_MANS_LAND;        /* demolish node */

    free(_node);
}

/*-------------------------------------------------------------------*/

Node* BinTreeCreateNode(void* _data)
{
    Node*   node = 0;

    node = (Node*)calloc(1,sizeof(node[0]));
    if (!node)
    {
        return 0;
    }

    node->m_data = _data;

    return node;
}

/*-------------------------------------------------------------------*/

BTreeIt BinTreeBegin(BinTree* _btree)
{
    assert(_btree);

    return (BTreeIt)_btree->m_begin;
}

/*-------------------------------------------------------------------*/

BTreeIt BinTreeEnd(BinTree* _btree)
{
    assert(_btree);

    return (BTreeIt)&_btree->m_end;
}

/*-------------------------------------------------------------------*/

BTreeIt BinTreeNext(BTreeIt _it)
{
    Node*   node = (Node*)_it;

    assert((Node*)_it);

    if (node->m_big)                                /* look for next node in the big subtree */
    {
        return (BTreeIt)BTNextBigChild(node->m_big);
    }

    while ( node->m_parent->m_small != node )       /* go up on the tree to the first node that has small child */
    {
        node = node->m_parent;
    }

    return (BTreeIt)node->m_parent;
}

/*-------------------------------------------------------------------*/

Node* BTNextBigChild(Node* _bigNode)
{
    assert(_bigNode);
    assert(_bigNode != (Node*)NO_MANS_LAND);

    while (_bigNode->m_small)                       /* go down on the small subtree till 0 is reached */
    {
        _bigNode = _bigNode->m_small;
    }

    return _bigNode;
}

/*-------------------------------------------------------------------*/

BTreeIt BinTreePrev(BTreeIt _it)
{
    Node*   node = (Node*)_it;

    assert((Node*)_it);
    assert((Node*)_it != (Node*)NO_MANS_LAND);

    if (node->m_data == (void*)NO_MANS_LAND)
    {
        return (BTreeIt)node->m_parent;
    }

    if (node->m_small)                                  /* look for prev node in the small subtree */
    {
        return (BTreeIt)BTPrevBigChild(node->m_small);
    }
                                                        /* go up on the tree to the first node that */
														/* you are his big child 					*/
    while ( node->m_parent && node->m_parent->m_big != node )
    {
        node = node->m_parent;
    }

    return (BTreeIt)node->m_parent;
}

/*-------------------------------------------------------------------*/

Node* BTPrevBigChild(Node* _smallNode)
{
    assert(_smallNode);

    while (_smallNode->m_big)                       /* go down on the big subtree till 0 is reached */
    {
        _smallNode = _smallNode->m_big;
    }

    return _smallNode;
}

/*-------------------------------------------------------------------*/

int BinTreeIsEqual(BTreeIt _iter1, BTreeIt _iter2)
{
    return (Node*)_iter1 == (Node*)_iter2;
}

/*-------------------------------------------------------------------*/

Node* BinTreeInsertRoot(BinTree* _btree,Node* _node)
{
    _btree->m_root           = _node;
    _btree->m_root->m_parent = 0;
    _btree->m_begin          = _node;
    _btree->m_end.m_parent   = _node;
    _btree->m_begin->m_small = &_btree->m_end;
    _btree->m_root->m_big    = &_btree->m_end;

    return _node;
}

/*-------------------------------------------------------------------*/

Node* BTSrchInsertNode(BinTree*_btree, Node* _root, Node* _node, int _mode)
{
    assert(_btree);
    assert(_node);
    assert(_root);

    if (!_btree->m_func(_root->m_data,_node->m_data))                   /* if node <= root */
    {
        if ( !_mode && !_btree->m_func(_node->m_data,_root->m_data))    /* if root <= node => root==node */
        {                                                               /* _mode == 0 => SEARCH mode     */
            return _root;
        }

        if (!_root->m_small || _root->m_small == &_btree->m_end)        /* there is no left subtree */
        {
            return BTSrchInsertRtrn(_btree,_root,&_root->m_small,_node,_mode); /* make insert for INSERT mode  */
                                                                               /* and return 0 for SEARCH mode */
        }

        return BTSrchInsertNode(_btree,_root->m_small,_node,_mode);     /* continue to left subtree */
    }

    if (!_root->m_big || _root->m_big == &_btree->m_end)                /* there is no right subtree */
    {
        return BTSrchInsertRtrn(_btree,_root,&_root->m_big,_node,_mode);/* make insert for INSERT mode  */
                                                                        /* and return 0 for SEARCH mode */
    }

    return BTSrchInsertNode(_btree,_root->m_big,_node,_mode);           /* continue to right subtree */
}

/*-------------------------------------------------------------------*/

Node* BTSrchInsertRtrn(BinTree* _btree,Node* _parent,OUT Node** _direcPtr,Node* _insNode,int _mode)
{
    if ( SEARCH == _mode)
    {
        return &_btree->m_end;                          /* in SEARCH mode no suitable node found   */
    }
    *_direcPtr         = _insNode;                      /* in INSERT mode connect _directRtr       */
                                                        /* {_parent->m_big or / _parent->m_small}  */
    _insNode->m_parent = _parent;                       /* to inserted node                        */

    return _insNode;
}

#ifdef BINTREE_UNITEST
/********************************************************************/
/*                        BINTREE_UNITEST                           */
/********************************************************************/
#define IS_SUCCESS(x)   !x ? "SUCCESS" : "FAILURE"

/*------------------    Forward Declaration     --------------------*/

void    BinTreeUnitest(void);
int     BinTreeRegresCheck(void);
int     CheckBinTreeInsert(void);
int     CompFunc(void* _param1, void* _param2);

/*-------------------------------------------------------------------*/
/*------------------    Test Functions     --------------------------*/

int main(void)
{
    BinTreeUnitest();
    return 0;
}

/*-------------------------------------------------------------------*/

void BinTreeUnitest(void)
{
    printf("BinTreeUnitest   %10s\n",IS_SUCCESS(BinTreeRegresCheck()));
}

int BinTreeRegresCheck(void)
{
    printf("BinTreeInsert   U_Test   %10s\n",IS_SUCCESS(CheckBinTreeInsert()));
    if (CheckBinTreeInsert())
    {
        return 1;
    }

    return 0;
}

int CompFunc(void* _param1, void* _param2)
{
    return *(int*)_param1<*(int*)_param2;
}

int CheckBinTreeInsert(void)
{
    BinTree*    btree       = 0;
    int         numArr[7]   = {8,5,3,6,10,15,20};
    BTreeIt     it;
    int         i;

    btree = BinTreeNew(CompFunc);
    assert(btree);

    for (i = 0 ; i<6 ; ++i )
    {
        it = BinTreeInsert(btree,&numArr[i]);
    }

    if (btree->m_begin->m_data != &numArr[2])
    {
        return 1;
    }
    if (btree->m_begin->m_small != &btree->m_end)
    {
        return 1;
    }
    if (btree->m_begin->m_parent->m_data != &numArr[1])
    {
        return 1;
    }
    if (btree->m_begin->m_parent->m_big->m_data != &numArr[3])
    {
        return 1;
    }

    it = BinTreeFind(btree,&numArr[1]);

    if (it == (BTreeIt)&btree->m_end)
    {
        return 1;
    }
    if (((Node*)it)->m_data != &numArr[1])
    {
        return 1;
    }

    it = BinTreeFind(btree,&numArr[6]);

    if (it != (BTreeIt)&btree->m_end)
    {
        return 1;
    }

    it = BinTreeBegin(btree);
    if  (((Node*)it)->m_data != &numArr[2])
    {
        return 1;
    }

    it = BinTreeNext(it);

    if (((Node*)it)->m_data != &numArr[1])
    {
        return 1;
    }

  /*  BinTreeDel(btree);*/
    return 0;
}

#endif /*#ifdef BINTREE_UNITEST*/
